package main

import "fmt"

func ShellSort(arr []int) {
	n := len(arr)
	gap := 1
	for gap < n/3 {
		gap = 3*gap + 1
	}
	for gap > 0 {
		for i := gap; i < n; i++ {
			temp := arr[i]
			var j int
			for j = i; j >= gap && arr[j-gap] > temp; j -= gap {
				arr[j] = arr[j-gap]
			}
			arr[j] = temp
		}
		gap /= 3
	}
}

func TestShellSort() {
	arr := []int{5, 2, 4, 6, 1, 3}
	fmt.Println("Before sorting:", arr)
	ShellSort(arr)
	fmt.Println("After sorting:", arr)
}
